package leetcode.other.greedy;

import java.util.Arrays;

/**
 * @Description:
 * 有n件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。
 * 在保证总重量不超过W的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
 * 比如：n = 3, W = 4, weights = {2, 1, 3}, values = {4, 2, 3}
 * 注意：每个物品只有1件，也就是每个物品只能选择0件或者1件，因此称为 0-1 背包问题
 * @Author Ammar
 * @Create 2023/7/3 10:04
 */
public class 背包 {
    public static void main(String[] args) {
        Article[] articles = new Article[]{
                new Article(35, 10),
                new Article(30, 40),
                new Article(60, 30),
                new Article(50, 50),
                new Article(40, 35),
                new Article(10, 40),
                new Article(25, 30)
        };
        Arrays.sort(articles, (Article o1, Article o2) -> {
            double r1 = o1.value / o1.weight;
            double r2 = o2.value / o2.weight;
            return r2 > r1 ? 1 : -1;
        });
        double capacity = 150;
        double weight = 0, value = 0;
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            double newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                weight = newWeight;
                value += articles[i].value;
                System.out.println("选择了第" + (i + 1) + "件物品，价值为" + articles[i].value);
            }
        }
        System.out.println("总价值为：" + value + "，总重量为：" + weight);
    }

    private static class Article {
        double weight;
        double value;

        public Article(double weight, double value) {
            this.weight = weight;
            this.value = value;
        }
    }
}
